package Algorithm.sort.basic;

import utils.CommonUtils;

import java.util.Arrays;

/**
 * 冒泡排序：从前往后依次对比两个相邻元素，若反序，则交换两个元素的位置，完成这样一趟冒泡后，此趟交换中最大的元素就“冒”到了表尾，这样就确定了一个元素
 *         的位置，然后继续对剩余的元素执行冒泡，直到确定所有元素位置。
 *
 * 优化：若在一趟冒泡中没有发生交换，则说明数组已经有序，可提前终止排序
 *
 * 性能：时间复杂度平均O(n2)，最好O(n)，最坏O(n2)。空间复杂度O(1)。稳定
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] A = new int[]{5,6,1,2,3,6,9};
        bubbleSort(A);
        System.out.println(Arrays.toString(A));
    }

    static void bubbleSort(int[] nums) {
        boolean flag = true;
        for (int i=nums.length-1;flag && i > 0;i--) {
            flag = false;//标记在一趟冒泡中是否发生过交换
            for (int j = 0;j < i;j++) {
                if (nums[j] > nums[j+1]) {
                    CommonUtils.swap(nums, j, j+1);
                    flag = true;
                }
            }
        }
    }
}
/**
 * 简评：在确定一个元素的位置时，选择排序是选出元素后直接与对应位置的元素交换，改变了剩余元素的相对次序，故选择排序是不稳定的，
 * 而冒泡排序是整体向后挪动，因此不会改变剩余元素的相对次序，故冒泡排序是稳定的
 */